{\magonebf 3.3 Stacks (stack) }

An instance $S$ of the data type $stack$ is 
a sequence of elements of a data type $E$, called the element 
type of $S$. Insertions or deletions of elements take place only at one end of 
the sequence, called the top of $S$. The size of $S$ is the length of the 
sequence, a stack of size zero is called the empty stack.

\bigskip
{\bf 1. Declaration  of a stack type}

\decl stack E

introduces a new data type with name \name\ consisting all all stacks with
element type $E$.


\bigskip
{\bf 2. Creation of a stack}

\create S {}   

creates an instance \var\ of type \name. \var\ is initialized with the empty 
stack.



{\bf 3. \operations}
\+\cleartabs & \hskip 2truecm & \hskip 4truecm &\cr
\+\op E       top   {}        
                              {returns the top element of \var}
\+\nop                        {\precond $S$ is not empty.}
\smallskip
\+\op E       pop   {}        
                              {deletes and returns the top element of \var}
\+\nop                        {\precond $S$ is not empty.}
\smallskip
\+\op E       push  {E\ x}    
                              {adds $x$ as new top element to \var.}
\smallskip
\+\op void    clear {}        
                              {makes \var\ the empty stack.}
\smallskip
\+\op int     size  {}        
                              {returns the size of \var.}
\smallskip
\+\op bool    empty {}        
                              {returns true if \var\ is empty, false otherwise.}

\bigskip
{\bf 4. Implementation}

Stacks are implemented by singly linked linear lists. All operations take 
time $O(1)$, except clear which takes time $O(n)$, where $n$ is the size of 
the stack.
